Profesor Szu
Limit pamięci: 32 MB
W mieście Bajtion ma swoją siedzibę bajtocki uniwersytet. Oprócz głównego
gmachu, uniwersytet ma do dyspozycji domków dla pracowników naukowych.
Domki połączone są jednokierunkowymi drogami, może jednak być wiele dróg
łączących dwa domki, istnieją także drogi łączące gmach uniwersytetu z
domkami (droga może łączyć także pewien obiekt z nim samym).
Bajtion został tak skonstruowany, żeby żadne drogi się
nie przecinały w miejscach innych niż domki lub gmach (ale mogą przebiegać
mostami i tunelami); ponadto każda droga
zaczyna się w pewnym domku lub w gmachu i kończy się w domku lub
w gmachu. Wiadomo ponadto, że istnieje co najmniej jedna droga łącząca
pewien domek z gmachem uniwersytetu.
Pewnego razu uniwersytet zapragnął zatrudnić u siebie znanego specjalistę
informatyki teoretycznej - profesora Szu. Jak wielu wielkich naukowców,
profesor Szu ma dziwny zwyczaj; otóż każdego dnia lubi dojeżdżać do gmachu
uniwersytetu inną trasą (będącą drogą bądź układem dróg, z których każda
następna zaczyna się w domku, w którym kończy się poprzednia; trasa może
przechodzić przez ten sam domek bądź główny gmach uniwersytetu
wielokrotnie). Profesor dwie trasy uważa za różne, jeżeli różnią się
chociaż jedną wykorzystaną drogą (przy czym kolejność dróg jest ważna, a
dwie różne drogi łączące te same domki uważa on za różne).
Znając schemat połączeń między domkami Bajtionu, pomóż uniwersytetowi
znaleźć domek, z którego istnieje najwięcej różnych tras do gmachu
uniwersytetu (zamieszkawszy w tym domku, profesor Szu będzie chciał
najdłużej pracować na uczelni) - jeżeli takich domków jest więcej niż
jeden, to podaj wszystkie z nich. Jeżeli przy tym z jakiegoś domku istnieje
więcej niż tras do gmachu, to zakładamy, że profesor może tam
zamieszkać na zawsze (jako że nie może żyć nieskończenie długo, a
lat to dość bezpieczna granica).
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia schemat połączeń między domkami Bajtionu,
- wyznaczy domki, w których profesor Szu mógłby mieszkać
najdłużej oraz najdłuższy czas jego zamieszkiwania,
- wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz
()
oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę domków
i liczbę dróg w Bajtionie (domki są ponumerowane liczbami od do ,
a umownie nadajemy gmachowi uniwersytetu numer ).
W wierszach o numerach od do znajdują się pary liczb
całkowitych , ( dla )
oddzielone pojedynczymi odstępami i oznaczające odpowiednio numer
domku w którym zaczyna się i numer domku w którym kończy się -ta
droga.
Wyjście
Pierwszy wiersz wyjścia powinien zawierać maksymalną liczbę dni jaką
profesor Szu może mieszkać w Bajtionie lub jedno słowo "zawsze", jeżeli
ta liczba przekracza dni. W drugim wierszu powinna się
znajdować liczba domków, zamieszkanie w których zapewnia profesorowi
okres pobytu podany w pierwszym wierszu wyjścia. W trzecim wierszu
powinny się znaleźć numery wszystkich takich domków, oddzielone
pojedynczymi odstępami i podane w kolejności rosnącej. Wszystkie domki,
w których profesor może zamieszkać na zawsze uważamy przy tym za jednakowo
dobre.
Przykład
Dla danych wejściowych:
3 5
1 2
1 3
2 3
3 4
3 4
poprawnym wynikiem jest:
4
1
1
Natomiast dla danych:
3 5
1 2
2 3
3 1
3 4
3 4
poprawnym wynikiem jest:
zawsze
3
1 2 3
Autor zadania: Jakub Radoszewski.